import java.io.*;
import java.nio.Buffer;
import java.util.*;


/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: ws
 * Date: 2023-04-04
 * Time: 21:17
 */
//public class Ceshi {
//    public static void main(String[] args) throws IOException {
//        //io 字符输入，输出，速度是Scanner的10倍
//        // 字符流缓冲区                               字符流输入          字节流
//        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
//        //String str = bf.readLine();
//        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
//        //打印流
//        PrintStream print = System.out;
//        Scanner scanner = new Scanner(System.in);
//        int a = scanner.nextInt();
//        // 输入一个数字后，回车\n 会留在缓冲区，被s 捕获，导致s 没有读取到需要的字符串
//        //解决方法
//        // 吃掉换行符
//        //scanner.nextLine();
//        //scanner.skip("\n");
//        String s = scanner.nextLine();
//        System.out.println(a);
//        System.out.println(s);
//    }
//}


public class Ceshi {
    public static int kmp(String str, String pattern) {
        // 计算pattern的next数组
        int[] next = getNext(pattern);

        int i = 0; // str的指针
        int j = 0; // pattern的指针
        while (i < str.length() && j < pattern.length()) {
            if (j == -1 || str.charAt(i) == pattern.charAt(j)) { // 当j=-1时，表示第一个字符就不匹配，所以i和j都要向右移动一位
                i++;
                j++;
            } else {
                j = next[j]; // 如果当前字符不匹配，则将j回溯到next[j]位置继续匹配
            }
        }
        if (j == pattern.length()) { // 匹配成功
            return i - j;
        } else {
            return -1; // 匹配失败
        }
    }

    private static int[] getNext(String pattern) {
        int[] next = new int[pattern.length()];
        next[0] = -1;
        int i = 0;
        int j = -1;
        while (i < next.length - 1) {
            if (j == -1 || pattern.charAt(i) == pattern.charAt(j)) {
                i++;
                j++;
                next[i] = j;
            } else {
                j = next[j];
            }
        }
        return next;
    }

    public static void main(String[] args) {
        String str = "ABCACDABCD";
        String pattern = "ABCD";
        int index = Ceshi.kmp(str, pattern);
        System.out.println(index); // 输出4，表示pattern字符串在str字符串中从第4个字符开始出现
    }

}


